package graph;

import java.util.*;


public class CourseSchedule207 {

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if(prerequisites==null||prerequisites.length==0){
            return true;
        }

        HashMap<Integer, List<Integer>> map = new HashMap<>();
        int[] degree = new int[numCourses];

        //初始化入度表
        for (int i = 0; i < degree.length; i++) {
            degree[i] = 0;
        }

        //初始化邻接图
        for (int i = 0; i < prerequisites.length; i++) {
            int[] edge = prerequisites[i];
            int pre = edge[1];
            int end = edge[0];
//            map.getOrDefault(pre, new ArrayList<>()).add(end);
            List<Integer> des = map.getOrDefault(pre, new ArrayList<>());
            des.add(end);
            map.put(pre,des);
            degree[end]++;
        }

        Deque<Integer> deque = new LinkedList<>();
        //将入度为0的放入队列中
        for (int i = 0; i < degree.length; i++) {
            if(degree[i]==0){
                deque.offer(i);
            }
        }

        //拓扑排序
        while (deque.size()!=0){
            Integer data = deque.poll();
            List<Integer> list = map.get(data);
            if(list!=null){
                for (int i = 0; i < list.size(); i++) {
                    degree[list.get(i)]--;
                    if(degree[list.get(i)]==0){
                        deque.offer(list.get(i));
                    }
                }
            }
        }

        //判断是否入度都能清零
        for (int i = 0; i < degree.length; i++) {
            if(degree[i]!=0){
                return false;
            }
        }
        return true;
    }

//        public boolean canFinish(int numCourses, int[][] prerequisites) {
//        boolean[] available = new boolean[numCourses];
//        for (int i = 0; i < available.length; i++) {
//            available[i] = false;
//        }
//        Map<Integer, List<Integer>> edges = new HashMap<>();
//        build(edges, prerequisites);
//        for (int i = 0; i < numCourses; i++) {
//            if (edges.get(i) == null) {
//                available[i] = true;
//                continue;
//            }
//            if(available[i]==true){
//                continue;
//            }
//            Set<Integer> visited = new HashSet<>();
//            visited.add(i);
//            LinkedList<Integer> q = new LinkedList<>(edges.get(i));
//            while (q.size()!=0){
//                int temp = q.poll();
//                if(visited.contains(temp)){
//                    return false;
//                }
//                if(available[temp]==true){
//                    continue;
//                }
//                visited.add(temp);
//                if(edges.get(temp)!=null){
//                    q.addAll(edges.get(temp));
//                }
//            }
//            for (int j:visited
//                 ) {
//                available[j]=true;
//            }
//        }
//        return true;
//    }
//
//    private void build(Map<Integer, List<Integer>> edges, int[][] prerequisites) {
//        for (int i = 0; i < prerequisites.length; i++) {
//            int[] temp = prerequisites[i];
//            List<Integer> list = edges.getOrDefault(temp[0], new ArrayList<>());
//            list.add(temp[1]);
//            edges.put(temp[0], list);
//        }
//    }
}
